#include<iostream.h>
#include<conio.h>
#include<math.h>

int board[20];
int count=0;
void queen(int row, int n);
void print_final(int n);
int place(int row, int column);

void main()
{
	clrscr();
	cout<<"\n \t \t Program to Demonstrate n-Queens Problem"<<endl;
	cout<<"\n \n Enter the number of Queens = ";
	int n;
	cin>>n;
	queen(1,n);
	getch();
}
void queen(int row, int n)
{
	int column;
	//cout<<"\n Inside Queen: \n";
	for(column=1;column<=n;column++)
	{       //cout<<"Column = "<<column<<" row = "<<row;
		if(place(row,column))
		{
			board[row]=column;
			if(row==n)
				print_final(n);
			else
			       queen(row+1,n);
		}
	}
}
int place(int row, int column)
{
	for(int i=1;i<=(row-1);i++)
	{
		if(board[i]==column)
			return 0;
		else
			if(abs(board[i]-column)==abs(i-row))
				return 0;
	}
	return 1;
}
void print_final(int n)
{       int i, j;
	cout<<"\n \n \n Solution: "<<++count;
	cout<<endl<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<"\t "<<i;
	}
	for(i=1;i<=n;i++)
	{
		cout<<"\n \n "<<i;
		for(j=1;j<=n;j++)
		{
			if(board[i]==j)
				cout<<"\t Q";
			else
				cout<<"\t *";
		}
	}
}
